#include "common.h"

int waysToStep(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;
	int ans;
	int a = 1, b = 2, c = 4;
	for (int i = 4; i <= n; i++)
	{
		ans = ((a + b) % 1000000007 + c) % 1000000007;
		a = b;
		b = c;
		c = ans;
	}
	return ans;
}
